/**
 * https://leetcode.cn/problems/kth-missing-positive-number/submissions/564307581/
 * 1539. 第 k 个缺失的正整数
 * easy 陈贝纯 2024.09.13
 * 二分搜索
 */

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n=arr.size();
        int d=arr[n-1]-0;
        if(d-n<k)
        return arr[n-1]+(k-(d-n));
        if(arr[0]-1>=k)
        return 0+k;
        int l=0;
        int ans=0;
        int r=n-1;
        while(r-l>=2){
            int mid=(l+r)/2;
            if(arr[mid]-(mid+1)<k){
                ans=mid;
                l=mid;
            }
            else
            r=mid;
        }
        cout<<ans<<endl;
        return arr[ans]+(k-(arr[ans]-(ans+1)));
    }
};